# coding=utf-8
#encoding: utf-8


''' 快速排序
原理：通过一趟扫描将要排序的数据分割成独立的两部分,
其中一部分的所有数据都比另外一部分的所有数据都要小,
然后再按此方法对这两部分数据分别进行快速排序,
整个排序过程可以递归进行

步骤：
1. 从数列中挑出一个元素，称为 “基准”（pivot），
2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边），
在这个分区退出之后，该基准就处于数列的中间位置，这个称为分区（partition）操作
3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序
'''


# 方法一：
def quick_sort_01(sort_list, left, right):
    # left：列表左边界下标，right：列表右边界下标
    # 如果只有一个数字，结束递归
    if left >= right:
        return
    # 默认以第一个数字作为基准
    flag = left
    for i in range(left+1, right+1):
        if sort_list[flag] > sort_list[i]:
            tmp = sort_list[i]
            # 删除元素
            del sort_list[i]
            # 将元素插入到指定元素前面一个位置，即将tmp插入到flag之前
            sort_list.insert(flag, tmp)
            flag += 1
            #print 'aa:', sort_list
    print sort_list
    # 将基准前后分别递归排序
    quick_sort_01(sort_list, left, flag-1)
    quick_sort_01(sort_list, flag+1, right)
    return sort_list


# 方法二：
def quick_sort_02(arr, left, right):
    # 只有left < right 排序
    if left < right:
        pivot_index = partition(arr, left, right)
        quick_sort_02(arr, left, pivot_index - 1)
        quick_sort_02(arr, pivot_index + 1, right)

def partition(arr, left, right):
    """找到基准位置, 并返回"""
    pivot_index = left
    pivot = arr[left]

    for i in range(left + 1, right + 1):
        if arr[i] < pivot:
            # 如果此处索引的值小于基准值, 基准值的位置后移一位
            # 并将后移一位的值和这个值交换, 让基准位置及之前的始终小于基准值
            pivot_index += 1
            if pivot_index != i:
                arr[pivot_index], arr[i] = arr[i], arr[pivot_index]

    # 将基准值移动到正确的位置
    arr[left], arr[pivot_index] = arr[pivot_index], arr[left]

    return pivot_index


list = [100,600,7,386,222,3,4,0,-2]
quick_sort_01(list, 0, 8)

